package main

import "fmt"

func main() {
	fmt.Println(LIS([]int{10, 20, 30, 1, 2, 3, 4}))
}

// 最长递增子序列
// 给定数组arr，设长度为n，输出arr的最长递增子序列。（如果有多个答案，请输出其中字典序最小的）

/**
 * retrun the longest increasing subsequence
 * @param arr int整型一维数组 the array
 * @return int整型一维数组
 */
func LIS(arr []int) []int {
	// 长度为i的最小末值
	// 第 i 位的值: 长度为 i + 1 的递增子序列中 i 位的最小值。
	// posMinVal 并不是一个实际存在的递增子序列。
	posMinVal := make([]int, 1, len(arr))
	// 长度对应数组位置Map
	lenToIndexMap := make(map[int][]int)

	posMinVal[0] = arr[0]
	lenToIndexMap[1] = []int{0}
	for i, val := range arr[1:] {
		if val > posMinVal[len(posMinVal)-1] {
			posMinVal = append(posMinVal, val)
			// fmt.Println(posMinVal)
			currentLen := len(posMinVal)
			lengthArr := lenToIndexMap[currentLen]
			if lengthArr == nil {
				lengthArr = []int{i + 1}
			} else {
				lengthArr = append(lengthArr, i+1)
			}
			lenToIndexMap[currentLen] = lengthArr
			// fmt.Println(lenToIndexMap)
		} else {
			for j, ele := range posMinVal {
				if ele > val {
					posMinVal[j] = val
					currentLen := j + 1
					lengthArr := lenToIndexMap[currentLen]
					if lengthArr == nil {
						lengthArr = []int{i + 1}
					} else {
						lengthArr = append(lengthArr, i+1)
					}
					lenToIndexMap[currentLen] = lengthArr
					break
				}
			}
		}
	}

	maxLen := len(posMinVal)
	maxLenArr := make([]int, maxLen, maxLen)

	lastMaxVal := posMinVal[maxLen-1] + 1
	lastMaxIndex := len(arr)

	// maxLenArr[maxLen-1] = lastMaxVal

	for i := maxLen; i >= 1; i-- {
		candidateIndexList := lenToIndexMap[i]
		minVal := lastMaxVal
		minIndex := 0
		for _, index := range candidateIndexList {
			val := arr[index]
			if index < lastMaxIndex && val < minVal {
				minVal = val
				minIndex = index
			}
		}
		lastMaxIndex = minIndex
		lastMaxVal = minVal
		maxLenArr[i-1] = minVal
	}

	return maxLenArr
}
